package first.forHuaWei.动态规划;

/**
 * @ClassName LC5
 * @description:
 * @author: 荣燊
 * @create: 2021-09-09 16:16
 **/
public class LC5 {
    // 最长回文字符串
    public static void main(String[] args) {

    }

    // 动态规划
    public static String longestPalindrome(String s) {
        int len = s.length();
        // s的第i位到第j位是否是回文字符串
        boolean[][] dp = new boolean[len][len];
        for (int i=0; i<len; i++) {
            dp[i][i] = true;
        }

        char[] chars = s.toCharArray();
        int maxLen = 1;
        int begin = 0; //记录左边界，因为最后要输出
        // l表示回文字符串长度
        for (int l=2; l<=len; l++) {
            for (int i=0; i<len; i++) {
                // 该回文字符串的长度，l
                int j = i + l - 1;
                // 如果j超过右边界
                if (j >= len) {
                    break;
                }
                // 开始动态规划
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else { // 如果两字符相同
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        // 因为j>=i,这里要求j-i>=2
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                // 求解最大的maxLen
                if (dp[i][j] && j-i+1 > maxLen) {
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin+maxLen);

    }
}
